import javax.activation.MailcapCommandMap;
import java.lang.reflect.Array;
import java.util.Arrays;

public class Solution174 {
    public int calculateMinimumHP(int[][] dungeon) {
        int rows = dungeon.length;
        if (rows == 0) return 0;
        int col = dungeon[0].length;
        int[] dp = new int[col + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[col - 1] = 1;
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = col - 1; j >=0; j--) {
                int min = Math.min(dp[j + 1], dp[j]);
                dp[j] = Math.max(1, min - dungeon[i][j]);
            }
        }
        return dp[0];
    }
}
